`
https://leetcode.cn/problems/minimum-path-sum/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const m = grid.length, n = grid[0].length
  const memo = new Array(m).fill().map(() => new Array(n).fill(-1));

  function dfs(i, j) {
    if (i >= m || j >= n) {
      return Infinity; // 越界，返回极大值
    }
    if (i === m - 1 && j === n - 1) {
      return grid[i][j]; // 终点
    }
    if (memo[i][j] !== -1) {
      return memo[i][j]; // 已经计算过
    }

    // 只能向右或向下移动
    const right = dfs(i, j + 1);
    const down = dfs(i + 1, j);

    // 当前节点的最小路径和 = 当前值 + 右或下的较小值
    memo[i][j] = grid[i][j] + Math.min(right, down);
    return memo[i][j];
  }

  return dfs(0, 0);
};